#pragma once

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;
/*HJJ QQ479287006
 *你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

 

示例 1：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/house-robber
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */
//这个是背包问题吗？ 卧槽不是 背包问题 妈的写背包写傻了
//dp 公式  dp[i]= max(dp[i-2]+nums[i],dp[i-1]) //dp[i-1] 判断拿不拿
//遍历顺序dp[i] 是根据dp[i - 2] 和 dp[i - 1] 推导出来的，那么⼀定是从前到后遍历！
//初始化 dp[0]=max(nums[0],nums[1]) dp[1]=max(nums[0],nums[1])
//todo 不算自己完全写的 我一直以为背包问题 偷偷看了一样
int rob(vector<int>& nums) {
    if (nums.size()<2)
        return nums[0];
    if (nums.size()==2)
        return max(nums[0],nums[1]);

    vector<int> dp(nums.size(),0);

    //初始化 dp[0]
    dp[0]=nums[0];
    dp[1]=max(nums[0],nums[1]);

    for (int i = 2; i <nums.size() ; ++i) {
        dp[i]=  max(dp[i-2]+nums[i],dp[i-1]);
    }

    return dp[nums.size()-1];
}



//int rob(vector<int>& nums) {
//    if (nums.size() == 0) return 0;
//    if (nums.size() == 1) return nums[0];
//    vector<int> dp(nums.size());
//    dp[0] = nums[0];
//    dp[1] = max(nums[0], nums[1]);
//    总结
//    打家劫舍是DP解决的经典题⽬，这道题也是打家劫舍⼊⻔级题⽬，后⾯我们还会变种⽅式来打劫的。
//    哈喽，我是Carl，代码随想录刷题⽹站已经上线了：www.programmercarl.com，200道经典题⽬的刷
//    题顺序，详细题解，⽀持C++、Java，Python，Go，JavaScript版本，去看看吧，⼀个只要你发现 就会
//    收藏的硬核算法学习⽹站！
//    Github项⽬同步：https://github.com/youngyangyang04/leetcode-master，star⽀持⼀波吧！
//    代码随想录算法精讲纸质版 即将出版 ，敬请期待！
//    同时我也在B站讲解算法视频，点击这⾥直达B站！
//    如果感觉PDF对你有帮助，微信搜索：代码随想录，关注我吧，你会发现相⻅恨晚！
//    打家劫舍II
//    213.打家劫舍II
//    题⽬链接：https://leetcode-cn.com/problems/house-robber-ii/
//    for (int i = 2; i < nums.size(); i++) {
//        dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
//    }
//    return dp[nums.size() - 1];
//}